package cn.cxd.leetcode;

import java.util.Comparator;
import java.util.PriorityQueue;
import java.util.Queue;

public class Leetcode42 {
    public int trap(int[] height) {
        int res = 0;

        Queue<Integer> leftQueue = new PriorityQueue<>(Comparator.reverseOrder());
        Queue<Integer> rightQueue = new PriorityQueue<>(Comparator.reverseOrder());

        for (int i = 1; i < height.length; i++) {
            rightQueue.offer(height[i]);
        }

        leftQueue.offer(height[0]);
        for (int i = 1; i < height.length - 1; i++) {
            int current = height[i];
            rightQueue.remove(current);
            int leftMax = leftQueue.peek();
            int rightMax = rightQueue.peek();
            int min = Math.min(leftMax, rightMax);
            int count = min - current > 0 ? min - current : 0;
            res += count;
            leftQueue.offer(current);
        }

        return res;
    }
}
